
import java.util.ArrayList;

/**
 * HuffmanTranslator.java
 * Descripción: Clase que, a partir de una cadena, genera el árbol de Huffman correspondiente
 *              y almacena el código generado en un diccionario, para posteriormente traducir los
 *              códigos ingresados.
 * @author Oscar Castañeda 11086
 * @since 11/09/2012
 * @version 1.5
 */
public class HuffmanTranslator {
    
    private Contador contador;  //Contador de carácteres para el traductor.
    private Dictionary diccionario; //Diccionario usado por el traductor.
    private HuffmanTree theTree; //HuffmanTree sobre el cual trabaja el traductor.
    private ArrayList<String> theChars; //Array list que contiene los caracteres individuales existentes en el HuffmanTree. 
    private ArrayList<Integer> theFrequencies; //Array list que contiene la frecuencia de los caracteres en correlación con el Array anterior.
    private ArrayList<String> theCodes; //Array list que contiene el código de los caracteres en correlación con los arrays anteriores.
    private Heap<HuffmanTree> theHeap; //Heap para ordenar los HuffmanTree.
    private static HuffmanTranslator theInstance;
    private static boolean yaInstanciada = false;
    
    /**
     * Construye un nuevo traductor.
     */
    private HuffmanTranslator(){
        contador = new Contador();
        diccionario = new Dictionary();
        theChars = new ArrayList(10);
        theFrequencies = new ArrayList(10);
        theCodes = new ArrayList(10);
        theHeap = new HuffmanHeap();
    }
    
    /**
     * Permite obtener la única instancia del traductor.
     * @return Instancia actual del HuffmanTranslator.
     */
    public static HuffmanTranslator getInstance(){
        if (!yaInstanciada){
            theInstance = new HuffmanTranslator();
            yaInstanciada = true;
        }
        return theInstance;
    }
    
    /**
     * Detruye la instancia única actual del traductor.
     */
    public static void destroyInstance(){
        yaInstanciada = false;
    }
    
    /**
     * Genera el HuffmanTree correspondiente a la cadena dada.
     * @param cadena Cadena que será convertida al código de Huffman.
     */
    public void generateHuffmanTree(String cadena){
        //Se convierte el texto ingresado a HuffmanAssociations.
        ArrayList<HuffmanAssociation> listaAsociaciones = contador.countIn(cadena);
        //Se recopilan los carácteres existentes, se convierten las asociaciones actuales a HuffmanTree
        //y se coloca cada árbol en el HuffmanHeap.
        for (HuffmanAssociation asociacion : listaAsociaciones){
            theChars.add(asociacion.getKey());
            theFrequencies.add(asociacion.getFrequency());
            HuffmanTree tree = new HuffmanTree(asociacion);
            theHeap.add(tree);
        }
        //Una vez añadidos todos los árboles, se sacaran los dos menores para generar un árbol, el cual entrará de nuevo al Heap,
        //hasta quedar solo un árbol.
        while(theHeap.size()>1){
            HuffmanTree smallTree1 = theHeap.getNext();
            HuffmanTree smallTree2 = theHeap.getNext();
            String newHuffmanTreeKey = smallTree1.getValue().getKey();
            newHuffmanTreeKey += smallTree2.getValue().getKey();
            int newHuffmanTreeFrequency = smallTree1.getValue().getFrequency();
            newHuffmanTreeFrequency += smallTree2.getValue().getFrequency();
            HuffmanTree mergedTree = new HuffmanTree(new HuffmanAssociation(newHuffmanTreeKey,newHuffmanTreeFrequency),smallTree1, smallTree2);
            theHeap.add(mergedTree);
        }
        //Al quedar solo un árbol, este es el árbol final. Tan solo se revisa que sí haya habido un árbol y que no estuviese vacío.
        if (!theHeap.isEmpty()){
            theTree = theHeap.getNext();
        }else{
            //Si el heap está vacío, el árbol será null.
            theTree = null;
        }
    }
    
    /**
     * Método recursivo que permite obtener el código para cada un caracter existente en el árbol.
     * @pre El HuffmanTree ya existe. El carácter indicado se encuentra dentro del árbol.
     * @post Se obtiene el código correspondiente al carácter indicado.
     * @param tree HuffmanTree a partir del cual se verá si ir al hijo izquierdo o derecho.
     * @param character Carácter cuyo código se está generando.
     * @param generatedCode String en el que se va guardando el código generado.
     * @return String con el código de Huffman correspondiente al carácter indidcado.
     */
    private String generateCodeFromTree(HuffmanTree tree,String character, String generatedCode){        
        //Se revisa que el actual árbol no sea una hoja, la cual, por la forma de construcción del HuffmanTree se identificaría por tener uno de sus hijos null.
        if((tree.getLeft() != null) || (tree.getRight() != null)){
            //Se observa si el carácter está en el árbol izquierdo,
            if(tree.getLeft().getValue().getKey().indexOf(character) >= 0){
                //Lo cual ocurrirá si su valor está contenido en el Key del HuffmanTree izquierdo (es decir que su index es distinto de -1)
                //En dicho caso, ya que se ha ido a la izquierda, se agrega un cero al código de Huffman.
                generatedCode += "0";
                //Se establece que el próximo árbol con el que se trabajará es el izquierdo.
                tree = (HuffmanTree) tree.getLeft();
            }else{
                //De lo contrario, dicho carácter debe de estar en el árbol derecho,
                //Así que se agrega un 1 al código generado.
                generatedCode += "1";
                //Y se establece que se trabajará próximamente con el árbol derecho.
                tree = (HuffmanTree) tree.getRight();
            }
            //Se repite el procedimiento recursivamente con el nuevo árbol a examinar.
            generatedCode = generateCodeFromTree(tree, character, generatedCode);
        }
        //Cuando se llegue a una hoja, se devolverá el código final.
        return generatedCode;
    }
    
    /**
     * @pre Ya se ha generado el HuffmanTree con una cadena semilla.
     * @post Se genera el Diccionario correspondiente.
     */
    public void generateDictionary(){
        //En generateCodeFromTree, si el HuffmanTree solo tiene la raiz, el código
        //generado será un string vacío. Para tomar en cuenta ese caso, se revisa 
        //si solo hay un carácter.
        if(theChars.size()==1){
            String character = theChars.get(0);
            //En dicho caso, se agrega el carácter al diccionario con el código
            //cero.
            theCodes.add("0");
            diccionario.add("0", character);
        }
        //Para cada uno de los carácteres existentes en el árbol
        for(String character : theChars){
            //Se genera su código de Huffman.
            String generatedCode = "";
            generatedCode = generateCodeFromTree(theTree, character, generatedCode);
            //Y se agrega al diccionario la pareja de código, carácter.
            diccionario.add(generatedCode, character);
            //También se agrega a la lista de control local de códigos.
            theCodes.add(generatedCode);
        }
    }
    
    /**
     * @pre El diccionario ya ha sido generado.
     * @post Se devuelve un String desencriptado utilizando el código de Huffman
     * actual.
     * @param binaryCode String encriptado con el código de Huffman correspondiente al estado actual del Traductor.
     * @return String desencriptado con el mensaje decodificado.
     */
    public String decode(String binaryCode) {
        String resultado = "";
        String fragmentoAnalizado = "";
        //Se recorre cada carácter de la cadena ingresada.
        for (int index = 0; index < binaryCode.length(); index++){
            //Se va acumulando un segmento de la cadena cuyo significado se desconoce.
            fragmentoAnalizado += binaryCode.substring(index, index+1);
            if (diccionario.hasDefinition(fragmentoAnalizado)){
                //Hasta hallarle significado. En dicho momento, se agrega a la cadena de resultado el carácter decodificado.
                resultado += diccionario.translate(fragmentoAnalizado);
                //Y se empieza a examinar un nuevo segmento de cadena.
                fragmentoAnalizado = "";
            }else{
                if(index == binaryCode.length()-1)
                    //Si no se le haya significado y ya se ha acabado la cadena, es porque hay un código incorrecto.
                    resultado = "CÓDIGO INCORRECTO";
            }
        }
        return resultado;              
    }

    
    /**
     * Devuelve un String que contiene los caracteres presentes en el HuffmanTree, su frecuencia y su código.
     * @return 
     */
    public String getTable(){
        String tabla = "________________________________________________________\n";
        tabla +=       "| Caracter | Frecuencia |      Código de Huffman        \n";
        tabla +=       "|__________|____________|_______________________________\n";
        for (int i= 0; i<theChars.size(); i++){
            tabla += "|     " + theChars.get(i) + "    |      " + theFrequencies.get(i)+"     | "+ theCodes.get(i) + "\n";
        }
        tabla +=       "|__________|____________|_______________________________";
        return tabla;
    }
    
    /**
     * @pre No hay precondiciones.
     * @post El HuffmanTranslator se reinicia, vaciando las cadenas que ha analizado,
     *       su diccionario, árbol, tree y heap.
     */
    public void reset(){
        contador.reset();
        diccionario.reset();
        theTree = null;
        theChars.clear();
        theFrequencies.clear();
        theCodes.clear();
        theHeap.reset();        
    }
}
